package leetcode;

/**
 * @Project : algorithm-learning-java
 * @Package : leetcode
 * @Author : Ruoyu Wang
 * @User : Momenta
 * @DateTime : 2024/1/17 15:35
 */
public class Q0221 {
    /**
     * O(n^3) O(n^3)
     */
//    public int maximalSquare(char[][] matrix) {
//        int res = 0;
//        int m = matrix.length;
//        int n = matrix[0].length;
//        int l = Math.min(m, n);
//        boolean[][][] f = new boolean[l][m][n];
//        for (int len = 0; len < l; len++) {
//            for (int i = 0, i2 = i + len; i2 < m; i++, i2++) {
//                for (int j = 0, j2 = j + len; j2 < n; j++, j2++) {
//                    f[len][i2][j2] = matrix[i2][j2] == '1';
//                    if (len > 0) {
//                        f[len][i2][j2] &= f[len - 1][i2 - 1][j2 - 1] && f[len - 1][i2][j2 - 1] && f[len - 1][i2 - 1][j2];
//                    }
//                    if (f[len][i2][j2]) res = Math.max(res, len + 1);
//                }
//            }
//            if (res != len + 1) return res * res;
//        }
//        return res * res;
//    }

    /**
     * O(n^3) O(n^2) 滚动数组优化
     */
//    public int maximalSquare(char[][] matrix) {
//        int res = 0;
//        int m = matrix.length;
//        int n = matrix[0].length;
//        int l = Math.min(m, n);
//        boolean[][] f = new boolean[m][n];
//
//        for (int i = 0; i < m; i++) {
//            for (int j = 0; j < n; j++) {
//                if (matrix[i][j] == '1') {
//                    f[i][j] = true;
//                    res = 1;
//                }
//            }
//        }
//
//        if (res == 0) return 0;
//
//        for (int len = 1; len < l; len++) {
//            for (int i = m - 1, pi = i - len; pi >= 0; i--, pi--) {
//                for (int j = n - 1, pj = j - len; pj >= 0; j--, pj--) {
//                    f[i][j] &= f[i - 1][j - 1] && f[i][j - 1] && f[i - 1][j];
//                    if (f[i][j]) res = Math.max(res, len + 1);
//                }
//            }
//            if (res != len + 1) return res * res;
//        }
//
//        return res * res;
//    }

    /**
     * O(n^3) O(n^2) 滚动数组优化
     */
    public int maximalSquare(char[][] matrix) {
        int res = 0;
        int[][] f = new int[matrix.length][matrix[0].length];

        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[0].length; j++) {
                if (matrix[i][j] == '1') {
                    if (i == 0 || j == 0) {
                        f[i][j] = 1;
                    } else {
                        f[i][j] = Math.min(Math.min(f[i - 1][j], f[i][j - 1]), f[i - 1][j - 1]) + 1;
                    }
                    res = Math.max(res, f[i][j]);
                }
            }
        }

        return res * res;
    }

    public static void main(String[] args) {
        Q0221 sl = new Q0221();
        char[][] matrix = {{'1', '0', '1', '0', '0'}, {'1', '0', '1', '1', '1'}, {'1', '1', '1', '1', '1'}, {'1', '0', '0', '1', '0'}};
        System.out.println(sl.maximalSquare(matrix));
    }
}
